package com.Sudoku;
// 数独游戏规则：将1~9填入9x9的盘面中，使每行、每列、每个粗线宫（3x3）内均不重复。
// 行：横排，从上到下依次为第1~9行；
// 列：竖排，从左到右依次为第1~9列；
// 宫：粗线围住的3x3小九宫，从左到右、从上到下依次为第1~9宫；
// 解：题目中初始已存在的数字，作为解题推理的基础依据；

import java.beans.PropertyChangeListener;
import java.beans.PropertyChangeSupport;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;

public class Sudoku {
	
	//添加对某个变量的监听，第一个参数是变量名，第二个是变量改变前的值，第二个是变量改变后的值
	private final PropertyChangeSupport propertyChanges = 
			        new PropertyChangeSupport(this);
    private int propertyState = 0;
 
	private volatile int msDemoStep = 200;
	private volatile boolean toStop = false;
	private volatile boolean isDemo = true;
	// Sudoku 现有多少棋局
	private int nGames = 1;
	// Sudoku 棋局行、列数
	private int nRow = 9;
	private int nCol = 9;
	// Sudoku in
	private int[][] problem = new int[nRow][nCol];
	// Sudoku out
	private int[][] solution = new int[nRow][nCol];
	// Sudoku for show
	private int[][] solushow = new int[nRow][nCol];
		
	// Map<Integer, Integer>: 位置 -> 价值
	private Map<Integer, Integer> cvMap = new HashMap<>();
	// Map<Integer, List>: 位置 -> 可用的数字列表 candidates
	private Map<Integer, List<Integer>> ccMap = new HashMap<>();

	private Random random = new Random();

	//--------------------------------------------------------
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int level = 1;
		Sudoku sudoku = new Sudoku(level);
		
		sudoku.hackGameSudoku();
		//sudoku.printListXY(xylist);
		
		System.out.println("#----------------------------");
		
	}

	// constructor
	public Sudoku() {
		super();
	}
	
	// constructor
	public Sudoku(int level) {
		// 首先计算有多少棋局可用, 现有45个
		nGames = SudokuProblems.problems.length;
		//System.out.println("problems.length：" + nGames);

		// 选定的 Sudoku 棋局: Level I, II, III, Master, Random
		if (level == 1) {
			deepCopyGame(SudokuProblems.problems[0], problem);
		}
		else if (level == 2) {
			deepCopyGame(SudokuProblems.problems[1], problem);
		}
		else if (level == 3) {
			deepCopyGame(SudokuProblems.problems[2], problem);
		}
		// Master
		else if (level == 4) {
			deepCopyGame(SudokuProblems.problems[nGames-1], problem);
		}
		// Random Game
		else if (level == 5){
			// + 3: 跳过前面的3个棋局
			int idx = getNextInt(nGames) + 3;
			if (idx >= nGames) {
				idx = nGames-2;
			}
			deepCopyGame(SudokuProblems.problems[idx], problem);
			System.out.println("Sudoku Game No.：" + (idx + 1));			
		}
		else {
			System.out.println("valid Sudoku Game!");
		}
	}

	// 直接传入一个数独
	public Sudoku(int[][] sudoku) {
		deepCopyGame(sudoku, problem);
		//printGameSudoku(problem);
	}

	//----------------------------- -----------------------------------
    public void addPropertyChangeListener(PropertyChangeListener listener) {
    	propertyChanges.addPropertyChangeListener(listener);
    	//System.out.println("addPropertyChangeLister: ");
    }

    public void removePropertyChangeListener(PropertyChangeListener listener) {
    	propertyChanges.removePropertyChangeListener(listener);
    	//System.out.println("removePropertyChangeLister: ");
    }

    // 当需要通知 Listener 时，执行如下语句
    // propertyChanges.firePropertyChange(String propertyName, Object oldValue, Object newValue) {

    public void resetDemoStep(int ms) {
    	msDemoStep = ms;
    	if (msDemoStep < 50) {
    		msDemoStep = 50;
    		isDemo = false;
    	}
    	if (msDemoStep > 1000) {
    		msDemoStep = 1000;
    	}
    	return; 
    }
    
    public void resetStopFlag(boolean bt) {
    	toStop = bt;
    	return; 
    }

	private void waitMS(int ms) {
		if( ms < 1)
			return;
		try {
			Thread.sleep(ms);
		} 
		catch (Exception e) {
			throw new RuntimeException("waitMS error: Thread.sleep");
		}		
	}
	
	// random.nextInt(n) 生成的随即数 [0,n-1]
	private int getNextInt(int up) {
		int rn = random.nextInt(up+1);
		return rn;
	}

	// 启动线程
	public void startSudokuThread() {
		// 生成一个匿名线程 并开始执行
		new Thread() {
			public void run() {
				System.out.println("Sudoku: Original Game ...");
				getProblemShow();
				propertyChanges.firePropertyChange("Sudoku", false, solushow);
				waitMS(900);
				waitMS(900);
				// 进入游戏,每一步的结果发送一次
				int status = hackGameSudoku();
				// 将进化状态返回给主程序，oldValue = status
				propertyChanges.firePropertyChange("Sudoku is over!", false, status);
				waitMS(msDemoStep);
			} // end run
		}.start();
	}

	// deep copy int[][] game1 --> game2
	private void deepCopyGame(int[][] game1, int[][] game2) {
		//int len = row*col;
		//System.arraycopy(gameCells1, 0, gameCells2, 0, len);
		for(int i=0; i<game1.length; i++) {
			for(int j=0; j<game1[0].length; j++) {
				game2[i][j] = game1[i][j];
			}
		}
	}

	// 0 表示空白
	private void clearGame(int[][] game) {
		for(int i=0; i<game.length; i++) {
			for(int j=0; j<game[0].length; j++) {
				game[i][j] = 0;
			}
		}
	}
	
	// is game over?
	private boolean isGameOver(int[][] game) {
		for(int i=0; i<game.length; i++) {
			for(int j=0; j<game[0].length; j++) {
				if (game[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}

	// is game applicable? 中间解可能不合适！
	private boolean isGameAppropriate(int[][] game) {
		evaluateGame(game, cvMap, ccMap);
		for(Entry<Integer, List<Integer>> entry : ccMap.entrySet()) {
			List<Integer> val = entry.getValue();
			if (val.size() == 0) {
				return false;
			}
			//System.out.println("value: " + entry.getValue());
		}
		return true;
	}

	// 
	private void printGameSudoku(int[][] game) {
		System.out.println("-------------------------");
		for(int i = 0; i<nRow; i++) {
			for(int j = 0; j<nCol; j++) {
				System.out.print(" " + game[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("-------------------------");		
	}

	// 
	private void printListXY(List<Integer> xylist) {
		int x, y;
		for(Integer k : xylist) {
			x = k/nCol;
			y = k%nCol;
			System.out.println("(" + x + ","+y + ")");
		}
	}
	
	// 根据一个 cell 的位置（x,y），计算所有相关的位置（x,y）, 共21个
	private List<Integer> getRelatedXY(int x, int y) {
		List<Integer> xyList = new ArrayList<Integer>();
		Set<Integer> xySet = new HashSet<Integer>();
		if (x<0 || x>8 || y<0 || y>8) {
			return null;
		}
		int r = x/3;
		int c = y/3;
		int xi, yj, pxy;
		// 3x3小宫格
		for(int i = 0; i<3; i++) {
			xi = r*3 + i;
			for(int j = 0; j<3; j++) {
				yj = c*3 + j;
				xySet.add(xi*nRow + yj);
			}
		}
		// 同一行的cell
		for(int k=0; k<nCol; k++) {
			xySet.add(x*nRow + k);
		}				
		// 同一列的cell
		for(int k=0; k<nRow; k++) {
			xySet.add(k*nCol + y);
		}
				
//		System.out.print("-------------------------");
		xyList.addAll(xySet);
		return xyList;
	}
	
	// 回溯法 解决 数独问题
	public int hackGameSudoku() {
		// problem -> solution
		deepCopyGame(problem, solution);
		// 回溯栈
		Stack<Acell> stack = new Stack<Acell>();
		
		// 有解=1，无解=2，强行终止=0
		int status = 0;
		boolean bt = false;
		int x, y;
		// 首先判断输入的问题是否合理？
		if(!isGameAppropriate(problem)) {
			status = 2;
			propertyChanges.firePropertyChange("Sudoku is over!", false, status);
			waitMS(msDemoStep);
			System.out.println("Sudoku is over!");
			return status;
		}
		// 快速解题，针对有些简单的数独问题
		while(!toStop) {
			bt = false;
			if (isGameOver(solution)) {
				status = 1;
				propertyChanges.firePropertyChange("Sudoku is over!", false, status);
				waitMS(msDemoStep);
				System.out.println("Sudoku is over!");
				return status;
			}
			// 评估每个空格的 价值 和 候选
			evaluateGame(solution,cvMap, ccMap);		
			// 填写具有唯一性的空格		
			for(Entry<Integer, List<Integer>> entry : ccMap.entrySet()) {
				int key = entry.getKey();
				List<Integer> val = entry.getValue();
				if (val.size() == 1) {
					x = key/nCol;
					y = key%nCol;
					solution[x][y] = val.get(0);
					bt = true;
				}
				//System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
			}
			// 发送中间结果
			getSoluShow();
			propertyChanges.firePropertyChange("Sudoku", false, solushow);
			waitMS(msDemoStep);
			// 数独没有结束
			if(!bt) {
				System.out.println("Sudoku is not over!");
				break;
			}
		} // while
		
		// 针对需要回溯的复杂数独问题
		Entry<Integer, List<Integer>> ccmap = null;
		Queue<Integer> qv = null;
		Acell acell = null;
		int pk = 0;
		while(!toStop) {
			if (isGameOver(solution)) {
				status = 1;
				propertyChanges.firePropertyChange("Sudoku is over!", false, status);
				waitMS(msDemoStep);
				System.out.println("Sudoku is over!");
				return status;
			}
			// 评估每个空格的 价值 和 候选
			evaluateGame(solution,cvMap, ccMap);
			ccmap = getMinEntry(ccMap);
			if (ccmap == null) {
				System.out.println("Sudoku is over!");
				status = 2; // 无解
				propertyChanges.firePropertyChange("Sudoku is over!", false, status);
				waitMS(msDemoStep);
				return status;
			}
			// 压入一个空格的候选值
			pk = ccmap.getKey();
			qv = new LinkedList<Integer>();
			qv.addAll(ccmap.getValue());
			x = pk/nCol;
			y = pk%nCol;				
			bt = false;
			while(!qv.isEmpty()) {
				Integer v = qv.peek();
				solution[x][y] = v;
				if (isGameAppropriate(solution)) {
					bt = true;
					stack.push(new Acell(pk, qv));
					break;
				}
				else {
					qv.poll();
				}
			} // while
			// 当前空格没有合适的填写，恢复原状，回溯到上一个空格
			if(!bt) {
				solution[x][y] = 0;
				while(!stack.isEmpty()) {
					acell = stack.pop();
					pk = acell.p;
					qv = acell.qv;
					x = pk/nCol;
					y = pk%nCol;
					if (qv.size() == 1) {
						solution[x][y] = 0;
					}
					else if(qv.size() > 1){
						qv.poll();
						Integer v = qv.peek();
						solution[x][y] = v;
						stack.push(new Acell(pk, qv));
						break;
					}
					else {
						System.out.println("Sudoku is over!");
						status = 2; // 无解
						propertyChanges.firePropertyChange("Sudoku is over!", false, status);
						waitMS(msDemoStep);
						return status;
					}
				}// while
				if (stack.isEmpty()) {
					System.out.println("Sudoku is over!");
					status = 2; // 无解
					propertyChanges.firePropertyChange("Sudoku is over!", false, status);
					waitMS(msDemoStep);
					return status;
				}
				
			}// if(!bt)
			// 发送中间结果
			if(isDemo) {
				getSoluShow();
				propertyChanges.firePropertyChange("Sudoku", false, solushow);
				waitMS(msDemoStep);
			}
		} // while
		
		return status;
	}
	
	// 在一个 Map 中找出最大值的项
	private Entry<Integer, Integer> getMaxEntry(Map<Integer, Integer> map) {
		Entry<Integer, Integer> max = null;
		for(Entry<Integer, Integer> entry : map.entrySet()) {
			int val = entry.getValue();
			if (max == null) {
				max = entry;
			}
			else if(val > max.getValue()) {
				max = entry;
			}
		}
		return max;
	}

	// 在一个 Map 中找出最小值的项
	private Entry<Integer, List<Integer>> getMinEntry(Map<Integer, List<Integer>> map) {
		Entry<Integer, List<Integer>> min = null;
		for(Entry<Integer, List<Integer>> entry : map.entrySet()) {
			List<Integer> val = entry.getValue();
			if (val.size() == 0)
				continue;
			if (min == null) {
				min = entry;
			}
			else if(min.getValue().size() > val.size()) {
				min = entry;
			}
		}
		return min;
	}

	// evaluate, rate game cells
	private void evaluateGame(int[][] prob, Map<Integer, Integer> cvMap, Map<Integer, List<Integer>> ccMap) {
		List<Integer> aList = new ArrayList<Integer>();
		List<Integer> vList = new ArrayList<Integer>();
		Set<Integer> vSet = new HashSet<Integer>();
		cvMap.clear();
		ccMap.clear();
		int x, y;
		for(int i=0; i<nRow; i++) {
			for(int j=0; j<nCol; j++) {
				int v = prob[i][j];
				if (v != 0) {
					continue;
				}
				// cell(i,j)相关的所有位置
				vList = getRelatedXY(i, j);
				aList.clear();
				vSet.clear();
				for(Integer k : vList) {
					x = k/nCol;
					y = k%nCol;
					if (i==x && j==y) {
						continue;
					}
					if (0==prob[x][y]) {
						continue;
					}
					aList.add(k);
					vSet.add(prob[x][y]);
				}
				// 对 cell 评分及候选
				int pij = i*nCol + j;
				cvMap.put(pij, aList.size());
				List<Integer> cList = new ArrayList<Integer>();
				for(int k=1; k<10; k++) {
					if(!vSet.contains(k)) {
						cList.add(k);
					}
				}
				// 在回溯过程中，cList可能是空的(上一次填写的不合理)
				ccMap.put(pij, cList);
//				if(!cList.isEmpty()) {
//				}
			}// for j
		}// for i
		return;
	}
	
	// problem + solution -> solushow (显示用的答案)
	private void getSoluShow() {
		deepCopyGame(solution, solushow);
		for(int i=0; i<nRow; i++) {
			for(int j=0; j<nCol; j++) {
				if (problem[i][j] > 0) {
					solushow[i][j] = problem[i][j] + 10;
				}
			}
		}
		return;
	}
	// 初始数独问题显示
	private void getProblemShow() {
		clearGame(solushow);
		for(int i=0; i<nRow; i++) {
			for(int j=0; j<nCol; j++) {
				if (problem[i][j] > 0) {
					solushow[i][j] = problem[i][j] + 10;
				}
				else {
					solushow[i][j] = 0;
				}
			}
		}
		// debug
		printGameSudoku(solushow);
		return;
	}

}

// 格子cell
class Acell {
	// cell的位置p:= i*nCol + j
	int p;
	//------------------------------------------------------- 
	// LinkedList类实现了Queue接口，可以把LinkedList当成Queue来用
	// add(), remove() 方法在失败的时候会抛出异常(不推荐)
	// queue.offer("a")  添加元素 
	// queue.poll() 返回第一个元素，并在队列中删除
	// PriorityQueue是一个基于优先级堆的优先级队列, 非阻塞队列。
	//--------------------------------------------------------
	Queue<Integer> qv = null; //new LinkedList<Integer>();
	
	Acell() {
		super();
	}
	// 
	public Acell(int p, List<Integer> q) {
		this.p = p;
		this.qv = new LinkedList<Integer>();
		this.qv.addAll(q);
	}
	//
	public Acell(int p, Queue<Integer> q) {
		this.p = p;
		this.qv = new LinkedList<Integer>();
		this.qv.addAll(q);
	}
	//
	public void set(List<Integer> q) {
		if(this.qv == null) 
			return;
		this.qv.clear();
		this.qv.addAll(q);
	}
	// 
	public void set(Queue<Integer> q) {
		if(this.qv == null) 
			return;
		this.qv.clear();
		this.qv.addAll(q);
	}

}